# CPU Scheduling
# 1. ์ค์ผ์ค๋ง
CPU ๋ฅผ ์ ์ฌ์ฉํ๊ธฐ ์ํด ํ๋ก์ธ์ค๋ฅผ ์ ๋ฐฐ์ ํ๊ธฐ
- ์กฐ๊ฑด : ์ค๋ฒํค๋ โ / ์ฌ์ฉ๋ฅ โ / ๊ธฐ์ ํ์ โ
- ๋ชฉํ
Batch System
: ๊ฐ๋ฅํ๋ฉด ๋ง์ ์ผ์ ์ํ. ์๊ฐ(time) ๋ณด๋จ ์ฒ๋ฆฌ๋(throughout)์ด ์ค์Interactive System
: ๋น ๋ฅธ ์๋ต ์๊ฐ. ์ ์ ๋๊ธฐ ์๊ฐ.Real-time System
: ๊ธฐํ(deadline) ๋ง์ถ๊ธฐ.
# 2. ์ ์ / ๋น์ ์ ์ค์ผ์ค๋ง
- ์ ์ (preemptive) : OS๊ฐ CPU์ ์ฌ์ฉ๊ถ์ ์ ์ ํ ์ ์๋ ๊ฒฝ์ฐ, ๊ฐ์ ํ์ํ๋ ๊ฒฝ์ฐ (์ฒ๋ฆฌ์๊ฐ ์์ธก ์ด๋ ค์)
- ๋น์ ์ (nonpreemptive) : ํ๋ก์ธ์ค ์ข ๋ฃ or I/O ๋ฑ์ ์ด๋ฒคํธ๊ฐ ์์ ๋๊น์ง ์คํ ๋ณด์ฅ (์ฒ๋ฆฌ์๊ฐ ์์ธก ์ฉ์ดํจ)
# 3. ํ๋ก์ธ์ค ์ํ
- ์ ์ ์ค์ผ์ค๋ง :
Interrupt
,I/O or Event Completion
,I/O or Event Wait
,Exit
- ๋น์ ์ ์ค์ผ์ค๋ง :
I/O or Event Wait
,Exit
ํ๋ก์ธ์ค์ ์ํ ์ ์ด
โย ์น์ธ (Admitted)ย : ํ๋ก์ธ์ค ์์ฑ์ด ๊ฐ๋ฅํ์ฌ ์น์ธ๋จ.
โย ์ค์ผ์ค๋ฌ ๋์คํจ์น (Scheduler Dispatch)ย : ์ค๋นย ์ํ์ ์๋ ํ๋ก์ธ์ค ์ค ํ๋๋ฅผ ์ ํํ์ฌ ์คํ์ํค๋ ๊ฒ.
โย ์ธํฐ๋ฝํธ (Interrupt)ย :ย ์์ธ,ย ์ ์ถ๋ ฅ, ์ด๋ฒคํธ ๋ฑ์ด ๋ฐ์ํ์ฌ ํ์ฌ ์คํย ์ค์ธ ํ๋ก์ธ์ค๋ฅผ ์ค๋น ์ํ๋ก ๋ฐ๊พธ๊ณ , ํด๋น ์์ ์ ๋จผ์ ์ฒ๋ฆฌํ๋ ๊ฒ.
โย ์ ์ถ๋ ฅ ๋๋ ์ด๋ฒคํธ ๋๊ธฐ (I/O or Event wait)ย : ์คํ ์ค์ธย ํ๋ก์ธ์ค๊ฐ ์ ์ถ๋ ฅ์ด๋ ์ด๋ฒคํธ๋ฅผ ์ฒ๋ฆฌํด์ผ ํ๋ ๊ฒฝ์ฐ, ์ ์ถ๋ ฅ/์ด๋ฒคํธ๊ฐ ๋ชจ๋ ๋๋ ๋๊น์ง ๋๊ธฐ ์ํ๋ก ๋ง๋๋ ๊ฒ.
โย ์ ์ถ๋ ฅ ๋๋ ์ด๋ฒคํธ ์๋ฃ (I/O or Event Completion)ย : ์ ์ถ๋ ฅ/์ด๋ฒคํธ๊ฐ ๋๋ ํ๋ก์ธ์ค๋ฅผ ์ค๋น ์ํ๋ก ์ ํํ์ฌ ์ค์ผ์ค๋ฌ์ ์ํด ์ ํ๋ ์ ์๋๋ก ๋ง๋๋ ๊ฒ.
# 4. CPU ์ค์ผ์ค๋ง์ ์ข ๋ฅ
๋น์ ์ ์ค์ผ์ค๋ง
- FCFS (First Come First Served)
- ํ์ ๋์ฐฉํ ์์๋๋ก CPU ํ ๋น
- ์คํ ์๊ฐ์ด ์งง์ ๊ฒ ๋ค๋ก ๊ฐ๋ฉด ํ๊ท ๋๊ธฐ ์๊ฐ์ด ๊ธธ์ด์ง
- SJF (Shortest Job First)
- ์ํ์๊ฐ์ด ๊ฐ์ฅ ์งง๋ค๊ณ ํ๋จ๋๋ ์์ ์ ๋จผ์ ์ํ
- FCFS ๋ณด๋ค ํ๊ท ๋๊ธฐ ์๊ฐ ๊ฐ์, ์งง์ ์์ ์ ์ ๋ฆฌ
- HRN (Hightest Response-ratio Next)
- ์ฐ์ ์์๋ฅผ ๊ณ์ฐํ์ฌ ์ ์ ๋ถํ๋ฑ์ ๋ณด์ํ ๋ฐฉ๋ฒ(SJF์ ๋จ์ ๋ณด์)
- ์ฐ์ ์์ = (๋๊ธฐ์๊ฐ + ์คํ์๊ฐ) / (์คํ์๊ฐ)
- FCFS (First Come First Served)
์ ์ ์ค์ผ์ค๋ง
Priority Scheduling
- ์ ์ /๋์ ์ผ๋ก ์ฐ์ ์์๋ฅผ ๋ถ์ฌํ์ฌ ์ฐ์ ์์๊ฐ ๋์ ์์๋๋ก ์ฒ๋ฆฌ
- ์ฐ์ ์์๊ฐ ๋ฎ์ ํ๋ก์ธ์ค๊ฐ ๋ฌดํ์ ๊ธฐ๋ค๋ฆฌ๋ Starvation ์ด ์๊ธธ ์ ์์
- Aging ๋ฐฉ๋ฒ์ผ๋ก Starvation ๋ฌธ์ ํด๊ฒฐ ๊ฐ๋ฅ
Round Robin
- FCFS์ ์ํด ํ๋ก์ธ์ค๋ค์ด ๋ณด๋ด์ง๋ฉด ๊ฐ ํ๋ก์ธ์ค๋ ๋์ผํ ์๊ฐ์
Time Quantum
๋งํผ CPU๋ฅผ ํ ๋ฌ ๋ฐ์Time Quantum
orTime Slice
: ์คํ์ ์ต์ ๋จ์ ์๊ฐ
- ํ ๋น ์๊ฐ(
Time Quantum
)์ด ํฌ๋ฉด FCFS์ ๊ฐ๊ฒ ๋๊ณ , ์์ผ๋ฉด ๋ฌธ๋งฅ ๊ตํ (Context Switching) ์ฆ์์ ธ์ ์ค๋ฒํค๋ ์ฆ๊ฐ
- FCFS์ ์ํด ํ๋ก์ธ์ค๋ค์ด ๋ณด๋ด์ง๋ฉด ๊ฐ ํ๋ก์ธ์ค๋ ๋์ผํ ์๊ฐ์
Multilevel-Queue (๋ค๋จ๊ณ ํ)
์์ ๋ค์ ์ฌ๋ฌ ์ข ๋ฅ์ ๊ทธ๋ฃน์ผ๋ก ๋๋์ด ์ฌ๋ฌ ๊ฐ์ ํ๋ฅผ ์ด์ฉํ๋ ๊ธฐ๋ฒ
์ฐ์ ์์๊ฐ ๋ฎ์ ํ๋ค์ด ์คํ ๋ชปํ๋ ๊ฑธ ๋ฐฉ์งํ๊ณ ์ ๊ฐ ํ๋ง๋ค ๋ค๋ฅธ
Time Quantum
์ ์ค์ ํด์ฃผ๋ ๋ฐฉ์ ์ฌ์ฉ์ฐ์ ์์๊ฐ ๋์ ํ๋ ์์
Time Quantum
ํ ๋น. ์ฐ์ ์์๊ฐ ๋ฎ์ ํ๋ ํฐTime Quantum
ํ ๋น.
Multilevel-Feedback-Queue (๋ค๋จ๊ณ ํผ๋๋ฐฑ ํ)
- ๋ค๋จ๊ณ ํ์์ ์์ ์
Time Quantum
์ ๋ค ์ฑ์ด ํ๋ก์ธ์ค๋ ๋ฐ์ผ๋ก ๋ด๋ ค๊ฐ๊ณ ์์ ์Time Quantum
์ ๋ค ์ฑ์ฐ์ง ๋ชปํ ํ๋ก์ธ์ค๋ ์๋ ํ ๊ทธ๋๋ก- Time Quantum์ ๋ค ์ฑ์ด ํ๋ก์ธ์ค๋ CPU burst ํ๋ก์ธ์ค๋ก ํ๋จํ๊ธฐ ๋๋ฌธ
- ์งง์ ์์ ์ ์ ๋ฆฌ, ์ ์ถ๋ ฅ ์์ฃผ(Interrupt๊ฐ ์ฆ์) ์์ ์ ์ฐ์ ๊ถ์ ์ค
- ์ฒ๋ฆฌ ์๊ฐ์ด ์งง์ ํ๋ก์ธ์ค๋ฅผ ๋จผ์ ์ฒ๋ฆฌํ๊ธฐ ๋๋ฌธ์ Turnaround ํ๊ท ์๊ฐ์ ์ค์์ค
- ๋ค๋จ๊ณ ํ์์ ์์ ์
# 5. CPU ์ค์ผ์ค๋ง ์ฒ๋
- Response Time
- ์์ ์ด ์ฒ์ ์คํ๋๊ธฐ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ
- Turnaround Time
- ์คํ ์๊ฐ๊ณผ ๋๊ธฐ ์๊ฐ์ ๋ชจ๋ ํฉํ ์๊ฐ์ผ๋ก ์์ ์ด ์๋ฃ๋ ๋ ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ
# ์ถ์ฒ
- ์ค์ผ์ค๋ง ๋ชฉํ : ๋งํฌ (opens new window)
- ํ๋ก์ธ์ค ์ ์ด๋ ๊ทธ๋ฆผ ์ถ์ฒ : ๋งํฌ (opens new window)
- CPU ์ค์ผ์ค๋ง ์ข ๋ฅ ๋ฐ ์ ์ ์ฐธ๊ณ : ๋งํฌ (opens new window)
- ๋ค๋จ๊ณํ ์ฐธ๊ณ : ๋งํฌ (opens new window)
- ๋ค๋จ๊ณ ํผ๋๋ฐฑ ํ ์ฐธ๊ณ : ๋งํฌ (opens new window)